package algorithm.leetcode.difficulty;

/**
 * 给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
 * 请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
 * 你可以假设 nums1 和 nums2 不会同时为空。
 *
 * @author jcak.wu
 * @version 1.0
 * @date 2020/8/17
 */
public class Question4 {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1 == null && nums2 == null) {
            return 0D;
        }
        int nums1Len = nums1 == null ? 0 : nums1.length;
        int nums2Len = nums2 == null ? 0 : nums2.length;

        if (nums2 == null) {
            return nums1Len % 2 == 0 ? (nums1[nums1Len / 2 - 1] + nums1[nums1Len / 2]) / 2.0 : nums1[nums1Len / 2];
        }
        if (nums1 == null) {
            return nums2Len % 2 == 0 ? (nums2[nums2Len / 2 - 1] + nums2[nums2Len / 2]) / 2.0 : nums2[nums2Len / 2];
        }

        int sumLen = nums1Len + nums2Len;
        int[] mergeArray = new int[sumLen];
        int num1Index = 0;
        int num2Index = 0;
        int index = 0;
        while (num1Index < nums1Len || num2Index < nums2Len) {
            if (num1Index == nums1Len) {
                while (num2Index < nums2Len) {
                    mergeArray[index++] = nums2[num2Index++];
                }
                break;
            }
            if (num2Index == nums2Len) {
                while (num1Index < nums1Len) {
                    mergeArray[index++] = nums1[num1Index++];
                }
                break;
            }
            int n1 = nums1[num1Index];
            int n2 = nums2[num2Index];
            if (n1 < n2) {
                mergeArray[index] = n1;
                num1Index++;
            } else {
                mergeArray[index] = n2;
                num2Index++;
            }
            index++;
        }
        return sumLen % 2 == 0 ? (mergeArray[sumLen / 2 - 1] + mergeArray[sumLen / 2]) / 2.0 : mergeArray[sumLen / 2];
    }

    public static void main(String[] args) {
        Question4 arrayMedian = new Question4();
        int[] nums1 = new int[]{1, 2};
        int[] nums2 = new int[]{3, 4};
        double medianNum = arrayMedian.findMedianSortedArrays(nums1, nums2);
        System.out.println(medianNum);

    }
}
